package com.peng.linkedlist;

import java.util.Arrays;
import java.util.Stack;

/**
 * 判断一个链表是否是回文结构
 */
public class Test02_IsPalindromeLIst {

    /**
     * 简单粗暴版，通过容器实现
     * need n extra space
     */
    public static boolean implement1(Node head) {
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        cur = head;
        while (!stack.isEmpty()) {
            if (stack.pop().value != cur.value) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }

    /**
     * 借助快慢指针，通过容器来实现
     * eed n/2 extra space
     *
     * @param head
     * @return
     */
    public static boolean implement2(Node head) {
        if (null == head || head.next == null) {
            return true;
        }
        //借助快慢指针，来到链表的中点（奇数为中点，偶数为上中点）的下一个位置
        Node slow = head.next;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时，slow代表的就是中点的下一个位置

        Stack<Node> stack = new Stack<>();
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }

        while (!stack.isEmpty()) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }

        return true;


    }

    /**
     * need O(1) extra space
     *
     * @param head
     * @return
     */
    public static boolean implement3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) {
            n1 = n1.next;
            n2 = n2.next.next;
        }

        //n1来到中点
        Node n3 = n1.next;
        n1.next = null;

        //对中点开始，往后的链表反转
        while (n3 != null) {
            n2 = n3.next;
            n3.next = n1;
            n1 = n3;
            n3 = n2;
        }
        //此时n1来到终点


        n3 = n1;//记录一下结尾位置，后面复原使用

        n2 = head;
        boolean result = true;
        while (n1 != null && n2 != null) {
            if (n1.value != n2.value) {
                result = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        //check完毕，把刚才反转的链表进行复原，即再进行一次反转
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }


        return result;


    }

    public static void main(String[] args) {

        Node head = LinkedListUtils.link(Arrays.asList(
                new Node(1),
                new Node(2),
                new Node(3),
                new Node(2),
                new Node(1)
        ));

//        LinkedListUtils.printNodes(head);
//        System.out.println(implement1(head));
//        System.out.println(implement2(head));
        System.out.println(implement3(head));

    }


}
